from typing import List


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)

        buy_dp = [0] * n
        frozen_dp = [0] * n
        sale_dp = [0] * n
        buy_dp[0] = -prices[0]
        for i in range(1, n):
            buy_dp[i] = max(buy_dp[i - 1], sale_dp[i - 1] - prices[i])
            frozen_dp[i] = max(buy_dp[i - 1] + prices[i], frozen_dp[i - 1])
            sale_dp[i] = max(sale_dp[i - 1], frozen_dp[i - 1])
            print(buy_dp, frozen_dp, sale_dp)
        return max(sale_dp[-1], frozen_dp[-1])


if __name__ == "__main__":
    res = Solution().maxProfit([1, 2, 3, 0, 2])
    print(res)

